数据结构由某一元素的集合和该集合中数据元素之间的关系组成。

依据数据元素之间的关系不同，数据结构分为两大类：线性结构和非线性结构。

线性结构

顺序表

顺序表是内存中连续存储多个元素的结构，在内存中的分配也是连续的，通过数组下标访问，下标从0开始。

image-20200714164706921

template <typename T>
class SeqList{
private:
    T* data;	//存放元素的起始地址
    int len;	//长度
    int size;	//容量
}

优点：

  1. 按照索引查询元素速度快
  2. 按照索引遍历数组方便

缺点：

  1. 数组的大小固定后就无法扩容了
  2. 数组只能存储一种类型的数据
  3. 添加，删除的操作慢，因为要移动其他的元素。

适用场景： 频繁查询，对存储空间要求不大，很少增加和删除的情况。

链表

链表是一种递归的数据结构，它或者为空（null），或者是指向一个结点（node）的引用，该节点还有一个元素和一个指向另一条链表的引用。

链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个结点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个结点地址的指针域。根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等。

template <typename T>
struct LinkNode
{
    T data;
    LinkNode<T> *link;
    LinkNode(LinkNode<T>* ptr = NULL){link == ptr;}
    LinkNode(const T& item, LinkNode<T>* ptr = NULL)
    {
        data = item;
        link = ptr;
    }
};

template <class T>
class LinkedList
{
 private:
    LinkNode<T> *head;
    int len;
}

单链表：image-20200714165745808

双向链表：image-20200714165757431

循环链表：image-20200714165811790优点：

  1. 链表是很常用的一种数据结构，不需要初始化容量，可以任意加减元素
  2. 添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可，所以添加，删除很快；

缺点：

  1. 因为含有大量的指针域，占用空间较大
  2. 查找元素需要遍历链表来查找，非常耗时。

适用场景：数据量较小，需要频繁增加，删除操作的场景

顺序表和链表的区别

存储分配的方式：

  1. 顺序表的存储空间是静态分配的
  2. 链表的存储空间是动态分配的

存储密度 = ${结点数据（data）本身所占的存储量 \over 结点结构所占的存储总量}$

  1. 顺序表的存储密度 = 1
  2. 链表的存储密度 < 1

插入/删除时移动元素个数：

  1. 顺序表平均需要移动近一半元素
  2. 链表不需要移动元素，只需要修改指针
  3. 若插入/删除仅发生在表的两端，宜采用带尾指针的循环链表

栈

栈是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。 栈的特点是：先进后出，或者说是后进先出，从栈顶放入元素的操作叫入栈，取出元素叫出栈。

栈的实现方式：

  • 数组形式：静态栈
  • 链表形式：动态栈

只能对栈顶元素进行操作。

顺序栈

使用数组实现，有固定大小。

template <typename T>
class seqStack{
private:
    T* elements;
    int top;
    int size;
    int increment;
}

image-20200714171002069

链栈

使用链表实现，无固定大小。

只定义栈顶指针。

template <typename T>
struct LinkNode{
    T data;
    LinkNode<T>* link;
    LinkNode(LinkNode<T>* ptr = NULL)
    {
        link = ptr;
    }
    LinkNode(const T& item, LinkNode<T>* ptr = NULL)
    {
        link = ptr;
        data = item;
    }
};
template <typename T>
class LinkedStack{
private:
    LinkNode<T>* top;
}

队列

队列与栈一样，也是一种线性表，不同的是，队列可以在一端添加元素，在另一端取出元素，也就是：先进先出。从一端放入元素的操作称为入队，取出元素为出队。

template <class T>
class SeqQueue
{
private:
    int rear, front;    // 队尾和队头指针
    T* elements;        //存放队列元素的数组
    int size;        //队列最大可容纳元素个数
}

非循环队列

插入时，队尾指针：rear++

image-20200714171920784

循环队列

插入时，队尾指针：rear = (rear + 1) % size

image-20200714171949671

非线性结构

二叉树

二叉树的性质：

  1. 非空二叉树第 i 层最多 2(i-1) 个结点 （i >= 1）
  2. 深度为 k 的二叉树最多 2k - 1 个结点 （k >= 1）
  3. 度为 0 的结点数为 n0，度为 2 的结点数为 n2，则 n0 = n2 + 1
  4. 有 n 个结点的完全二叉树深度 k = ⌊ log2(n) ⌋ + 1
  5. 对于含 n 个结点的完全二叉树中编号为 i （1 <= i <= n） 的结点
    1. 若 i = 1，为根，否则双亲为 ⌊ i / 2 ⌋
    2. 若 2i > n，则 i 结点没有左孩子，否则孩子编号为 2i
    3. 若 2i + 1 > n，则 i 结点没有右孩子，否则孩子编号为 2i + 1
typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

二叉树顺序存储：

image-20200715114213227

  • 顺序存储一般只用于完全二叉树，非完全二叉树使用顺序存储时需要空出很多内存，原因是：
    • left_child = parent * 2;
    • right_child = parent * 2 + 1;

二叉树链式存储：

image-20200715114333346

二叉树遍历方式：

  • 先序遍历：先访问根节点，然后访问左子树， 最后访问右子树。
  • 中序遍历：先访问左子树，然后访问根节点， 最后访问右子树。
  • 后续遍历：先访问左子树，然后访问右子树， 最后访问根节点。
  • 层次遍历

先序遍历、后序遍历可以确定根节点

中序遍历可以确定左子树和右子树

按照规律，可通过递归还原树

树的存储表示：

  • 广义表表示法

    image-20200715114800569

  • 父指针表示法

    image-20200715114816296

  • 子女链表表示法

    image-20200715114829138

  • 子女-兄弟链表表示法（左指针指向子女，右指针指向兄弟）

    image-20200715114924227

二叉树分支

满二叉树

  • 深度为 k 的二叉树最多 2k - 1 个结点 （k >= 1）
  • 深度为 k 的满二叉树有 2k - 1 个结点 （k >= 1）

完全二叉树

  • 深度为 k 的二叉树，除第 k 层外，各层结点都达到最大个数（k >= 1），且第 k 层所有的结点都连续集中在最左边
  • 堆一般都是用完全二叉树来实现的
    • 大顶堆：根 >= 左 && 根 >= 右
    • 小顶堆：根 <= 左 && 根 <= 右

二叉查找树

二叉查找树也叫二叉搜索树，或称二叉排序树（Binary Sort Tree），或者是一棵空树，或者是具有下列性质的二叉树：

  • 左 < 根 < 右
    • 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值
    • 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值
  • 任意节点的左、右子树也分别为二叉查找树
  • 查找、插入的时间复杂度较低为 O ( log ⁡ n )
  • 对二叉查找树进行中序遍历，即可得到有序的数列

平衡二叉树

简称AVL树

定义：基于二分法的策略提高数据的查找速度的一种二叉树数据结构；

特点：平衡二叉树是采用二分法思想把数据按规则组装成一个树形结构的数据，用这个树形结构的数据减少无关数据的检索，大大的提升了数据检索的速度

平衡二叉树的数据结构组装过程遵循以下规则：

  • 非叶子节点只能允许最多两个子节点存在
  • 每一个非叶子节点数据分布规则为左边的子节点小当前节点的值，右边的子节点大于当前节点的值(这里值是基于自己的算法规则而定的，比如hash值)

平衡二叉树特点：

  • 树的左右两边的层级数相差不会大于1，| 左子树树高 - 右子树树高 | <= 1
  • 平衡二叉树必定是二叉搜索树，反之则不一定
  • 没有值相等重复的节点
  • 非叶子节点最多拥有两个子节点
  • 最小二叉平衡树的节点的公式：F(n)=F(n-1)+F(n-2)+1 （1 是根节点，F(n-1) 是左子树的节点数量，F(n-2) 是右子树的节点数量）

image-20200715150417233

平衡树的层级结构：因为平衡二叉树查询复杂度和树的层级（h高度）成反比，h值越小查询越快，为了保证树的左右两端数据大致平衡以降低二叉树的查询难度一般会采用一种算法机制实现节点数据结构的平衡，实现了这种算法的有比如AVL、Treap、红黑树等，使用平衡二叉树能保证数据的左右两边的节点层级相差不会大于1，这样可以避免树形结构由于删除增加变成线性链表进而影响查询效率。保证数据平衡的情况下查找数据的速度近于二分法查找。

  • 最小失衡树：平衡二叉树插入新结点导致失衡的子树：调整：

    • LL型：根的左孩子右旋
    • RR型：根的右孩子左旋
    • LR型：根的左孩子左旋，再右旋
    • RL型：右孩子的左子树，先右旋，再左旋

红黑树

  • 每个结点是红色或黑色。（红或黑）
  • 根结点是黑色。（根黑）
  • 所有叶子节点都是黑色（叶结点即指树尾端NIL指针或NULL结点）。 （叶黑）
  • 如果一个结点是红的，那么它的两个儿子都是黑的。 （红子黑）
  • 对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。（路径下黑相同）

image-20200720220512006

调整方式：

  • 变色
  • 左旋
  • 右旋

应用：STL中的map和set

红黑树、B 树、B+ 树的区别？

  • 红黑树的深度比较大，而 B 树和 B+ 树的深度则相对要小一些
  • B+ 树则将数据都保存在叶子节点，同时通过链表的形式将他们连接在一起。

哈夫曼树

Huffman Tree

哈夫曼树是一种带权路径长度最短的二叉树，也称为最优二叉树。

一般可以按下面步骤构建：

  1. 根据给定的 n 个权值，构造具有 n 棵扩充二叉树的森林
  2. 在森林中选出两棵根节点的权值最小的树作为一棵新树的左，右子树，且置新树的附加根节点的权值为其左，右子树上根节点的权值之和。注意，左子树的权值应小于右子树的权值
  3. 从森林中删除这两棵树，同时把新树加入到森林中
  4. 重复2，3步骤，直到森林中只有一棵树为止，此树便是哈夫曼树

哈夫曼树的应用：哈夫曼编码，即如何让电文中出现较多的字符采用尽可能短的编码且保证在译码时不出现歧义。

B树

B树（B-tree）属于多叉树又名平衡多路查找树（查找路径不只两个），是一种自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。B树，概括来说是一个一般化的二叉查找树（binary search tree），可以拥有最多2个子节点。

与自平衡二叉查找树不同，B树适用于读写相对大的数据块的存储系统，例如磁盘。由于相比于磁盘IO的速度，内存中的耗时几乎可以省略，所以只要树的高度足够低，IO次数足够小，就可以提升查询性能。

  1. m阶代表一个树节点最多有多少个查找路径，m=m路,当m=2则是2叉树,m=3则是3叉

  2. 根结点至少有两个子女。

  3. 每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m

  4. 每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m

  5. 所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null

  6. 每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划

  7. 排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则

    image-20200720223510251

B+树

B+ 树是一种树数据结构，通常用于关系型数据库（如Mysql）和操作系统的文件系统中。

B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。

  • B+ 树元素自底向上插入，这与二叉树恰好相反。

  • 在B树基础上，为叶子结点增加链表指针（B树+叶子有序链表），所有关键字指针都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中。

  • b+树的非叶子节点不保存数据，只保存子树的临界值（最大或者最小），所以同样大小的节点，b+树相对于b树能够有更多的分支，使得这棵树更加矮胖，查询时做的IO操作次数也更少。

这通常在多数节点在次级存储比如硬盘中的时候出现。通过最大化在每个内部节点内的子节点的数目减少树的高度，平衡操作不经常发生，而且效率增加了。

image-20200720224453522

B树和B+树的同和异

特点：

  • 一般化的二叉查找树（binary search tree）
  • “矮胖”，内部（非叶子）节点可以拥有可变数量的子节点（数量范围预先定义好）

应用：大部分文件系统、数据库系统都采用B树、B+树作为索引结构

优点比较：

  • B树：对于在内部节点的数据，可直接得到，不必根据叶子节点来定位。如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快。
  • B+树：
    • B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，一个内部节点可以定位更多的叶子节点，且树的层级更少所以查询数据更快
    • B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定
    • B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高
    • B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描

区别分析

  • B+树中只有叶子节点会带有指向记录的指针（ROWID），而B树则所有节点都带有，在内部节点出现的索引项不会再出现在叶子节点中。
  • B+树中所有叶子节点都是通过指针连接在一起，而B树不会。

B树：

image-20200720224744197

B+树：

image-20200720224800081

总结

  1. 相同思想和策略

    从平衡二叉树、B树、B+树总体来看它们的贯彻的思想是相同的，都是采用二分法和数据平衡策略来提升查找数据的速度；

  2. 不同的方式的磁盘空间利用

    不同点是他们一个一个在演变的过程中通过IO从磁盘读取数据的原理进行一步步的演变，每一次演变都是为了让节点的空间更合理的运用起来，从而使树的层级减少达到快速查找数据的目的；

八叉树

八叉树（octree），或称八元树，是一种用于描述三维空间（划分空间）的树状数据结构。八叉树的每个节点表示一个正方体的体积元素，每个节点有八个子节点，这八个子节点所表示的体积元素加在一起就等于父节点的体积。一般中心点作为节点的分叉中心。

image-20200715151219530

应用：

  • 三维计算机图形
  • 最邻近搜索

散列表

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

构造方法：

  • 直接定址法
  • 除留余数法
  • 数字分析法
  • 折叠法
  • 平方取中法

处理冲突的方法：

  • 开散列方法：链地址法，key 相同的用单链表链接

  • 闭散列方法

    • 线性探测法：key 相同 -> 放到 key 的下一个位置，Hi = (H(key) + i) % m

      typedef char KeyType;

typedef struct {
	KeyType key;
}RcdType;

typedef struct {
	RcdType *rcd;
	int size;
	int count;
	bool *tag;
}HashTable;

      image-20200715113356751

    • 二次探测法：key 相同 -> 放到 Di = 1^2, -1^2, ..., ±（k)^2,(k<=m/2）

    • 随机探测法：H = (H(key) + 伪随机数) % m

广义表

头尾链表存储表示

// 广义表的头尾链表存储表示
typedef enum {ATOM, LIST} ElemTag;
// ATOM==0：原子，LIST==1：子表
typedef struct GLNode {
    ElemTag tag;
    // 公共部分，用于区分原子结点和表结点
    union {
        // 原子结点和表结点的联合部分
        AtomType atom;
        // atom 是原子结点的值域，AtomType 由用户定义
        struct {
            struct GLNode *hp, *tp;
        } ptr;
        // ptr 是表结点的指针域，prt.hp 和 ptr.tp 分别指向表头和表尾
    } a;
} *GList, GLNode;

image-20200715113545525

扩展线性链表存储表示

// 广义表的扩展线性链表存储表示
typedef enum {ATOM, LIST} ElemTag;
// ATOM==0：原子，LIST==1：子表
typedef struct GLNode1 {
    ElemTag tag;
    // 公共部分，用于区分原子结点和表结点
    union {
        // 原子结点和表结点的联合部分
        AtomType atom; // 原子结点的值域
        struct GLNode1 *hp; // 表结点的表头指针
    } a;
    struct GLNode1 *tp;
    // 相当于线性链表的 next，指向下一个元素结点
} *GList1, GLNode1;

image-20200715113804217

参考文章

平衡二叉树、B树、B+树，B*树的区别与联系

数据结构之树